package mdp;

public class longestPalindrome {
    //暴力会超时，虽然已经做了一定的剪枝
    // public String longestPalindrome(String s) {
    //     int l=s.length();
    //     //分奇偶
    //     int row=0,col=0,max=1;
    //     boolean[][]dp = new boolean[l][l];
    //     //右上角有用
    //     for(int i=0;i<l;i++){
    //         dp[i][i]=true;
    //     }
    //     for(int i=0;i<l;i++){
    //         for(int j=i;j<l;j++){
    //             if(i==j){
    //                 continue;
    //             }
    //             if(checkPalindrome(s.substring(i,j+1))&&(j-i+1)>max){
    //                 row=i;
    //                 col=j;
    //                 max=j-i+1;
    //             }
    //         }
    //     }
    //     return s.substring(row, col+1);
    // }
    // public boolean checkPalindrome(String s){
    //     for(int i=0;i<s.length()/2;i++){
    //         if(s.charAt(i)!=s.charAt(s.length()-1-i)){
    //             return false;
    //         }
    //     }

    //     return true;
    // }
    public String longestPalindrome(String s) {
        //对于长度大于2的，ij，则i+1和j-1也是回文
        int row=0,col=0;
        if(s.length()==1){
            return s;
        }else if(s.length()==2){
            return s.charAt(0)==s.charAt(1)?s:s.substring(0,1);
        }
        boolean[][]dp= new boolean[s.length()][s.length()];
        //初始化
        for(int i=0;i<s.length();i++){
            dp[i][i]=true;
        }
        for(int l=2;l<=s.length();l++){
            for(int i=0;i<s.length();i++){
                int j=i+l-1;
                if (j>=s.length()) {
                    break;
                }
                if(l==2){
                    if(s.charAt(i)==s.charAt(j)){
                        dp[i][j]=true;
                        if(l>col-row){
                            row=i;
                            col=j;
                        }
                    }
                }else{
                    //aba   abba
                    if(s.charAt(i)==s.charAt(j)&&dp[i+1][j-1]){
                        dp[i][j]=true;
                        if(l>col-row){
                            row=i;
                            col=j;
                        }
                    }
                }
            }
        }
        return s.substring(row, col+1);
    }
    public static void main(String[] args) {
        mdp.longestPalindrome obj = new longestPalindrome();
        // String s ="cbbd";
        // String s ="babad";
        String s ="ccc";
        System.out.println(obj.longestPalindrome(s));
    }
}
